/* Copyright (C) 1997-2005, Antony L Hosking.
 * All rights reserved.  */
package Canon;

import java.util.*;
import Translate.Temp;
import Translate.Tree;
import Translate.Tree.Exp;
import Translate.Tree.Exp.*;
import Translate.Tree.Stm;
import Translate.Tree.Stm.*;

public class Canon implements Tree.Visitor<LinkedList<Stm>, Exp> {
    static Stm SEQ(Stm a, Stm b) {
        if (a == null)
            return b;
        if (b == null)
            return a;
        return new SEQ(a, b);
    }

    public Exp visit(SEQ s, LinkedList<Stm> l) {
        s.left.accept(this, l);
        s.right.accept(this, l);
        return null;
    }

    public Exp visit(LABEL s, LinkedList<Stm> l) {
        l.add(s);
        return null;
    }

    public Exp visit(JUMP s, LinkedList<Stm> l) {
        s = new JUMP(s.exp.accept(this, l), s.targets);
        l.add(s);
        return null;
    }

    public Exp visit(MOVE s, LinkedList<Stm> l) {
        s = new MOVE(s.dst.accept(this, l), s.src.accept(this, l));
        if (s.dst instanceof TEMP || Tree.isAtom(s.src)) {
            l.add(s);
            return null;
        }
        Temp t = new Temp();
        l.add(new MOVE(new TEMP(t), s.src));
        l.add(new MOVE(s.dst, new TEMP(t)));
        return null;
    }

    public Exp visit(ESTM s, LinkedList<Stm> l) {
        l.add(new ESTM(s.exp.accept(this, l)));
        return null;
    }

    public Exp visit(CJUMP s, LinkedList<Stm> l) {
        reorder(s, l);
        return null;
    }

    public Exp visit(MEM e, LinkedList<Stm> l) {
        e = new MEM(e.exp.accept(this, l), e.offset);
        if (Tree.isAtom(e.exp))
            return e;
        Temp t = new Temp();
        l.add(new MOVE(new TEMP(t), e.exp));
        e = new MEM(new TEMP(t), e.offset);
        return e;
    }

    public Exp visit(TEMP e, LinkedList<Stm> l) {
        return e;
    }

    public Exp visit(ESEQ e, LinkedList<Stm> l) {
        e.stm.accept(this, l);
        return e.exp.accept(this, l);
    }

    public Exp visit(NAME e, LinkedList<Stm> l) {
        return e;
    }

    public Exp visit(CONST e, LinkedList<Stm> l) {
        return e;
    }

    public Exp visit(CALL e, LinkedList<Stm> l) {
        return reorder(e, l);
    }

    public Exp visit(BINOP e, LinkedList<Stm> l) {
        return reorder(e, l);
    }

    private Exp reorder(Stm s, LinkedList<Stm> l) {
        Exp[] kids = s.kids();
        reorder(kids, l);
        l.add(s.clone(kids));
        return null;
    }

    private Exp reorder(Exp e, LinkedList<Stm> l) {
        Exp[] kids = e.kids();
        reorder(kids, l);
        return e.clone(kids);
    }

    private void reorder(Exp[] exps, LinkedList<Stm> l) {
        boolean commute = true;
        LinkedList<Stm> stms = null;
        for (int i = exps.length; --i >= 0;) {
            LinkedList<Stm> s = new LinkedList<Stm>();
            Exp e = exps[i].accept(this, s);
            if (s.size() != 0)
                commute = false;
            if (commute && Tree.isAtom(e))
                exps[i] = e;
            else {
                Temp t = new Temp();
                exps[i] = new TEMP(t);
                s.add(new MOVE(new TEMP(t), e));
            }
            if (stms != null)
                s.addAll(stms);
            stms = s;
        }
        if (stms != null)
            l.addAll(stms);
    }

    public Canon(Stm s, LinkedList<Stm> l) {
        s.accept(this, l);
    }
}
